package com.zp.self.module.level_4_算法练习.算法.位图;

/**
 * @author By ZengPeng
 */
public class 力扣_547_省份数量 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_547_省份数量().findCircleNum(new int[][]{{1,1,0},{1,1,0},{0,0,1}}));
        System.out.println(new 力扣_547_省份数量().findCircleNum(new int[][]{{1,0,0},{0,1,0},{0,0,1}}));
        System.out.println(new 力扣_547_省份数量().findCircleNum(new int[][]{{1,0,0,1},{0,1,1,0},{0,1,1,1},{1,0,1,1}}));
    }

    /**
    题目：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，
     且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
     省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
     给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
     而 isConnected[i][j] = 0 表示二者不直接相连。
     返回矩阵中 省份 的数量。

     示例 1：
     输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
     输出：2

     示例 2：
     输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
     输出：3

    分析：【P 💝💝💝💝】
       1.位图记录：哪些城市已经被连接使用，遍历到时：如果已经被使用，则不能+1   -- 方法行不通：因为只能记录前面的与当前是否连接，不知道当前与后面的连接情况
       2.递归+位图==动态规划：找到关联的点时，要遍历下去：找出所有关联的节点，递归下去，找出次节点关联的所有节点【次节点已经被遍历过则跳出】
                --执行用时：1 ms, 在所有 Java 提交中击败了87.00%的用户

    边界值 & 注意点：
       1.
     **/
    public int findCircleNum(int[][] isConnected) {
       // 2.递归+位图：找到关联的点时，要遍历下去：找出所有关联的节点，递归下去，找出次节点关联的所有节点【次节点已经被遍历过则跳出】
        int count=0;
        boolean[] used = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if(!used[i]) {
                count++;
                used[i]=true;
                for (int j = 0; j < isConnected[0].length; j++) {
                   if(i!=j && isConnected[i][j]==1){
                       dfs(isConnected,used,j);
                   }
                }
            }
        }
        return count;

        //1.位图记录
        /*int count=0;
        boolean[] used = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if(!used[i]) count++;
            used[i]=true;
            for (int j = 0; j < isConnected[0].length; j++) {
                if(isConnected[i][j]==1 && !used[j])
                    used[j]=true;
            }
        }
        return count;*/
    }

    private void dfs(int[][] isConnected, boolean[] used, int row) {
        used[row]=true;
        for (int j = 0; j < isConnected[0].length; j++) {
            if(row!=j && isConnected[row][j]==1 && !used[j]){
                dfs(isConnected,used,j);
            }
        }
    }
}
